package com.xie.leetcode.array;

//229. 求众数 II
//        给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
//
//
//
//
//
//        示例 1：
//
//        输入：[3,2,3]
//        输出：[3]
//        示例 2：
//
//        输入：nums = [1]
//        输出：[1]
//        示例 3：
//
//        输入：[1,1,1,3,3,2,2,2]
//        输出：[1,2]
//
//
//        提示：
//
//        1 <= nums.length <= 5 * 104
//        -109 <= nums[i] <= 109
//
//
//        进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。

import java.util.*;

/**
 * @author xiezhendong
 * @date 2021/10/26
 */
public class MajorityElement2 {

    public static void main(String[] args) {
        MajorityElement2 majorityElement = new MajorityElement2();
        System.out.println(majorityElement.majorityElement(new int[]{3, 2, 3}));
        System.out.println(majorityElement.majorityElement(new int[]{1}));
        System.out.println(majorityElement.majorityElement(new int[]{1, 1, 1, 3, 3, 2, 2, 2}));
    }


    public List<Integer> majorityElement(int[] nums) {
        List<Integer> numsList = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return numsList;
        }
        int number = nums.length / 3;
        HashMap<Integer, Integer> numsMap = new HashMap<Integer, Integer>();
        for (int num : nums) {
            if (numsList.contains(num)) {
                continue;
            }
            numsMap.merge(num, 1, Integer::sum);
            if (numsMap.get(num) > number) {
                numsList.add(num);
            }
        }
        return numsList;
    }

    /**
     * 暴力遍历
     *
     * @param nums
     * @return
     */
    public List<Integer> majorityElement1(int[] nums) {
        List<Integer> numsList = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return numsList;
        }
        HashMap<Integer, Integer> numsMap = new HashMap<Integer, Integer>();

        for (int num : nums) {
            numsMap.merge(num, 1, Integer::sum);
        }
        int number = nums.length / 3;
        for (Map.Entry<Integer, Integer> entry : numsMap.entrySet()) {
            if (entry.getValue() > number) {
                numsList.add(entry.getKey());
            }
        }
        return numsList;
    }
}
